package com.mlh.violent;

public class DigitalTriangle {
    public static void main(String[] args) {
        int[][]triangle=new int[][]{
                {7,0,0,0,0},
                {3,8,0,0,0},
                {8,1,0,0,0},
                {2,7,4,4,0},
                {4,5,2,6,5}
        };
        solve(triangle);
    }
    public static void solve(int[][] triangle){
        //int[][]path=new int[triangle.length][triangle[0].length];记录最大值走的路径  感觉只能倒推获得
        //定义数组元素的意义：到达res[i][j]时路径的最大值
        int[][]res=new int[triangle.length][triangle[0].length];
        //初始化
        res[0][0]=7;
        for(int i=1;i<res.length;i++){
            res[i][0]=res[i-1][0]+triangle[i][0];//初始化垂直边的值
            res[i][i]=res[i-1][i-1]+triangle[i][i];//初始化斜边的值
        }
        for(int i=2;i<triangle.length;i++){
            for(int j=1;j<i;j++){
                //递推关系式
                res[i][j]=Math.max(res[i-1][j],res[i-1][j-1])+triangle[i][j];
            }
        }
        //打印输出res数组
        for(int i=0;i<res.length;i++){
            for(int j=0;j<res[0].length;j++){
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }
    }
}
